package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _515_largestValues {
    //BFS
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null){return res;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            //每轮循环遍历处理一层节
            int size = queue.size();
            int maxValue = Integer.MIN_VALUE;
            for(int i=0; i<size; i++){
                TreeNode curr = queue.poll();
                maxValue = Math.max(maxValue, curr.val);
                if(curr.left!=null){queue.add(curr.left);}
                if(curr.right!=null){queue.add(curr.right);}
            }
            res.add(maxValue);

        }
        return res;
    }

    public List<Integer> largestValues1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preOrder(root, 0, res);
        return res;
    }

    private void preOrder(TreeNode node, int currLevel, List<Integer> res){
        if(node==null){return;}
        //处理当前遍历
        if(res.size()==currLevel){
            res.add(node.val);
        }else {
            int maxValue = Math.max(res.get(currLevel), node.val);
            res.set(currLevel, maxValue);
        }

        preOrder(node.left, currLevel+1, res);
        preOrder(node.right, currLevel+1, res);
    }

}
